﻿<?xml version="1.0" encoding="utf-8"?><!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html>
<!-- saved from url=(0033)http://research.microsoft.com/pex -->
<head><link rel="StyleSheet" href="er.common.css" type="text/css" /><script src="er.common.js" type="text/javascript"> </script><link rel="SHORTCUT ICON" href="favicon.ico" /><link rel="icon" href="favicon.ico" type="image/x-icon" /><title>C:\Users\AO\Documents\Visual Studio 2010\AutomaTones3\automatones\AutomaTones\AutomaTones\Model\Automaton Model\RuleLib\GameOfLife.cs</title></head><body><div class="banner"></div><h2 id="top">C:\Users\AO\Documents\Visual Studio 2010\AutomaTones3\automatones\AutomaTones\AutomaTones\Model\Automaton Model\RuleLib\GameOfLife.cs</h2><div class="toggle"><p class="copyright"><a class="usercodeundertestcovered">user code under test</a>, 
  <span class="usercodeundertestnotcovered">user code under test (not covered)</span>, 
  <a class="userortestcodecovered">user code or test</a>, 
  <span class="userortestcodenotcovered">user code or test (not covered)</span>,
  <span class="tagged">tagged</span></p><table><tr><th>Methods</th></tr><tr><th /></tr></table><div class="toggle"><a class="button" href="#ID0EL">first</a><pre class="coverage">using System;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;
using Microsoft.Pex.Framework;
using Microsoft.Pex.Framework.Validation;

namespace AutomaTones.Model.Automaton_Model.RuleLib {
    /// &lt;author&gt;Anders Øland / anoe@itu&lt;/author&gt;
    /// &lt;summary&gt;
    /// Provides the rule used for the classic CA called Game of Life - invented by Jonh Conway in the 1970's.&lt;br&gt;&lt;/br&gt;&lt;br&gt;&lt;/br&gt;
    /// This simple rule generates an impressive diversity of behaviour:
    /// If a black cell has 2 or 3 black neighbours, it stays black. If a black cell has less than 2 or more than 3
    /// black neighbours it becomes white. If a white cell has 3 black neighbours, it becomes black.
    /// &lt;br&gt;&lt;/br&gt;&lt;br&gt;&lt;/br&gt;
    /// This class also facilitates easy setup of a Game of Life CA, as well as the adding of known patterns to a CA. 
    /// &lt;/summary&gt;
    [PexClass]
    public static partial class GameOfLife {
        /// &lt;summary&gt;
        /// The rule used for the classic CA called Game of Life.&lt;br&gt;&lt;/br&gt;&lt;br&gt;&lt;/br&gt; 
        /// If a black cell has 2 or 3 black neighbours, it stays black. If a black cell has less than 2 or more than 3
        /// black neighbours it becomes white. If a white cell has 3 black neighbours, it becomes black.
        /// &lt;br&gt;&lt;/br&gt;&lt;br&gt;&lt;/br&gt;
        /// This particular rule has been modified so it can handle state spaces which are not binary.
        /// Thus, if a live cell stays alive in the next generation its state is increased with one.
        /// If the new state &gt; space max ==&gt; new state = 1
        /// &lt;/summary&gt;
        public static int GameOfLifeRule(Cell cell, ref IEnumerable&lt;Rule.StateAtCoordinate&gt; statesOfNeighbours,
                                         params int[] unused) <span id="ID0EL"><a class="button" href="#top">top</a>|<a class="button" href="#ID0EFAAC">next</a></span><a class="userortestcodecovered">{</a>
            Contract.Requires(null != cell);
            Contract.Requires(0 == cell.State.SpaceMin);
            Contract.Requires(1 == cell.State.SpaceMax);
            Contract.Requires(Contract.ForAll(statesOfNeighbours, sn =&gt; 2 == sn.Position.Coord.Length));
            Contract.Requires(Contract.ForAll(statesOfNeighbours, sn =&gt; cell.State.SpaceMin &lt;= sn.State
                                                                        &amp;&amp; cell.State.SpaceMax &gt;= sn.State));
            Contract.Ensures(cell.State.SpaceMin &lt;= Contract.Result&lt;int&gt;());
            Contract.Ensures(cell.State.SpaceMax &gt;= Contract.Result&lt;int&gt;());
            <a class="userortestcodecovered">var blackNeighbours = (from n in statesOfNeighbours
                                   where </a><a class="button" href="#ID0EL">prev</a>|<span id="ID0EFAAC"><a class="button" href="#top">top</a>|<a class="button" href="#ID0EREAC">next</a></span><a class="userortestcodecovered">n.State != 0</a><a class="userortestcodecovered">
                                   select n).Count();</a>

            <a class="userortestcodecovered">var newState = 0;</a>
            <a class="userortestcodecovered">if (0 != cell.State.CurrentState)</a>
                <a class="userortestcodecovered">newState = (blackNeighbours == 2 || blackNeighbours == 3) ? 1 : 0;</a>
            else <a class="userortestcodecovered">newState = blackNeighbours == 3 ? 1 : 0;</a>
            <a class="userortestcodecovered">newState = newState == 0 ? 0 : 1 + cell.State.CurrentState;</a>
            <a class="userortestcodecovered">return newState &gt; cell.State.SpaceMax ? 1 : newState;</a>
        <a class="userortestcodecovered">}</a>

        /// &lt;summary&gt;
        /// Sets up a Cellular Automaton for Game of Life.
        /// &lt;/summary&gt;
        /// &lt;param name="size"&gt;Size of the dimensions of the rectangular 2-dimensional grid&lt;/param&gt;
        /// &lt;param name="stateSpace"&gt;&lt;/param&gt;
        /// &lt;returns&gt;Game of Life CA&lt;/returns&gt;
        [PexMethod, PexAllowedException(typeof(OverflowException))]
        public static CellularAutomaton SetupGameOfLife(uint size, uint stateSpace = 2u) <a class="button" href="#ID0EL">prev</a>|<span id="ID0EREAC"><a class="button" href="#top">top</a>|<a class="button" href="#ID0EXHAC">next</a></span><a class="userortestcodecovered">{</a>
            Contract.Requires(0 &lt; size);
            Contract.Requires(1 &lt; stateSpace);
            Contract.Ensures(size == Contract.Result&lt;CellularAutomaton&gt;().DimensionSize);
            Contract.Ensures(2 == Contract.Result&lt;CellularAutomaton&gt;().Dimensions);
            // Create a Rule instance
            <a class="userortestcodecovered">Rule gofRule = GetGofRule();</a>

            // Create a CellularAutomaton instance
            <a class="userortestcodecovered">CellularAutomaton gameOfLifeCA = new CellularAutomaton(2, size, gofRule, 0, (int) stateSpace - 1);</a>
            <a class="userortestcodecovered">return gameOfLifeCA;</a>
        <a class="userortestcodecovered">}</a>

        /// &lt;summary&gt;
        /// Get a new GOF Rule instance.
        /// &lt;/summary&gt;
        /// &lt;returns&gt;&lt;/returns&gt;
        public static Rule GetGofRule() <a class="button" href="#ID0EL">prev</a>|<span id="ID0EXHAC"><a class="button" href="#top">top</a>|<a class="button" href="#ID0E2IAE">next</a></span><a class="userortestcodecovered">{</a>
            Contract.Ensures(8 == Contract.Result&lt;Rule&gt;().Neighbourhood.Count);
            Contract.Ensures(2 == Contract.Result&lt;Rule&gt;().Dimensions);
            Contract.Ensures(GameOfLifeRule == Contract.Result&lt;Rule&gt;().MyRuleDelegate);
            <a class="userortestcodecovered">Rule gofRule = new Rule(2, GameOfLifeRule);</a>

            // Setup the coordinates for the neighbours which the rule uses 
            <a class="userortestcodecovered">var neighbourhood = new[] {
                                          new[] {-1, 1}, new[] {0, 1}, new[] {1, 1}, new[] {1, 0},
                                          new[] {1, -1}, new[] {0, -1}, new[] {-1, -1}, new[] {-1, 0}
                                      };</a>

            <a class="userortestcodecovered">foreach</a> (<a class="userortestcodecovered">int[] n</a> <a class="userortestcodecovered">in</a> <a class="userortestcodecovered">neighbourhood</a>) <a class="userortestcodecovered">gofRule.AddNeighbour(n);</a>
            <a class="userortestcodecovered">return gofRule;</a>
        <a class="userortestcodecovered">}</a>

        /// &lt;summary&gt;
        /// Demo game of life in the console.
        /// Press a key + return to evolve.
        /// &lt;/summary&gt;
        public static void GameOfLifeDemo(GofPattern pattern, int g) {
            CellularAutomaton gameOfLifeCA = SetupGameOfLife(75, 2);

            AddGofPattern(gameOfLifeCA, pattern, 20, 20);

            while (0 &lt; g--) {
                Console.Clear();
                Console.WriteLine(gameOfLifeCA + "\n");
                gameOfLifeCA.Evolve();
//                Console.Read();
            }
// ReSharper disable FunctionNeverReturns
        }
// ReSharper restore FunctionNeverReturns

        /// &lt;summary&gt;
        /// Adds a GofPattern to the Game of Life automaton, centered around the given coordinate.
        /// &lt;/summary&gt;
        /// &lt;param name="gofAutomaton"&gt;&lt;/param&gt;
        /// &lt;param name="gofPattern"&gt;&lt;/param&gt;
        /// &lt;param name="xPos"&gt;&lt;/param&gt;
        /// &lt;param name="yPos"&gt;&lt;/param&gt;
        [PexMethod(MaxConstraintSolverTime = 2)]
        public static void AddGofPattern(CellularAutomaton gofAutomaton, GofPattern gofPattern, int xPos = 0,
                                         int yPos = 0) <a class="button" href="#ID0EL">prev</a>|<span id="ID0E2IAE"><a class="button" href="#top">top</a></span><a class="userortestcodecovered">{</a>
            Contract.Requires(null != gofAutomaton);
            Contract.Requires(2 == gofAutomaton.Dimensions);
            <a class="userortestcodecovered">int[] pattern = Patterns[(int) gofPattern];</a>
            <a class="userortestcodecovered">int xSize = pattern[0],</a> <a class="userortestcodecovered">ySize = pattern[1];</a>
            <a class="userortestcodecovered">int deltaX = xSize / 2,</a> <a class="userortestcodecovered">deltaY = ySize / 2;</a>

            for (<a class="userortestcodecovered">int y = 0;</a> <a class="userortestcodecovered">y &lt; ySize</a>; <a class="userortestcodecovered">y++</a>) <a class="userortestcodecovered">{</a>
                for (<a class="userortestcodecovered">int x = 0;</a> <a class="userortestcodecovered">x &lt; xSize</a>; <a class="userortestcodecovered">x++</a>) <a class="userortestcodecovered">{</a>
                    <a class="userortestcodecovered">gofAutomaton[x - deltaX + xPos, y - deltaY + yPos] = pattern[2 + x + y * xSize];</a>
                <a class="userortestcodecovered">}</a>
            <a class="userortestcodecovered">}</a>
        <a class="userortestcodecovered">}</a>

        /// &lt;summary&gt;
        /// A collection of interesting patterns for Game of Life.
        /// To add them to your cellular automaton use the AddGofPattern method.
        /// &lt;/summary&gt;
        public enum GofPattern {
            Blinker,
            Toad,
            Beacon,
            Pulsar,
            Block,
            Beehive,
            Loaf,
            Boat,
            Glider,
            LightweightSpaceship,
            RPentomino,
            Diehard,
            Acorn,
            InfiniteGrowth1,
            InfiniteGrowth2,
            InfiniteGrowth3,
            GosperGliderGun
        }

// Oscillator Patterns:
        public static readonly int[] Blinker = new[] {
                                                         // Dimensions
                                                         3, 1,
                                                         // Pattern
                                                         1, 1, 1
                                                     };

        public static readonly int[] Toad = new[] {
                                                      // Dimensions                                
                                                      4, 2,
                                                      // Pattern
                                                      0, 1, 1, 1,
                                                      1, 1, 1, 0
                                                  };

        public static readonly int[] Beacon = new[] {
                                                        // Dimensions                                
                                                        4, 4,
                                                        // Pattern
                                                        1, 1, 0, 0,
                                                        1, 0, 0, 0,
                                                        0, 0, 0, 1,
                                                        0, 0, 1, 1,
                                                    };

        public static readonly int[] Pulsar = new[] {
                                                        // Dimensions
                                                        15, 15,
                                                        // Pattern
                                                        0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
                                                        0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
                                                        0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0,
                                                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                                                        1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1,
                                                        0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0,
                                                        0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0,
                                                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                                                        0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0,
                                                        0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0,
                                                        1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1,
                                                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                                                        0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0,
                                                        0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
                                                        0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0
                                                    };

// Still Lives Patterns:
        public static readonly int[] Block = new[] {
                                                       // Dimensions                                
                                                       2, 2,
                                                       // Pattern
                                                       1, 1,
                                                       1, 1
                                                   };

        public static readonly int[] Beehive = new[] {
                                                         // Dimensions                                
                                                         4, 3,
                                                         // Pattern
                                                         0, 1, 1, 0,
                                                         1, 0, 0, 1,
                                                         0, 1, 1, 0
                                                     };

        public static readonly int[] Loaf = new[] {
                                                      // Dimensions                                
                                                      4, 4,
                                                      // Pattern
                                                      0, 1, 1, 0,
                                                      1, 0, 0, 1,
                                                      0, 1, 0, 1,
                                                      0, 0, 1, 0,
                                                  };

        public static readonly int[] Boat = new[] {
                                                      // Dimensions                                
                                                      3, 3,
                                                      // Pattern
                                                      1, 1, 0,
                                                      1, 0, 1,
                                                      0, 1, 0,
                                                  };

// Spacehip Patterns:
        public static readonly int[] Glider = new[] {
                                                        // Dimensions                                
                                                        3, 3,
                                                        // Pattern
                                                        0, 1, 0,
                                                        0, 0, 1,
                                                        1, 1, 1,
                                                    };

        public static readonly int[] LightweightSpaceship = new[] {
                                                                      // Dimensions                                
                                                                      5, 4,
                                                                      // Pattern
                                                                      1, 0, 0, 1, 0,
                                                                      0, 0, 0, 0, 1,
                                                                      1, 0, 0, 0, 1,
                                                                      0, 1, 1, 1, 1
                                                                  };

// Methuselah Patterns - can evolve for a long time before stabilizing
        /// &lt;summary&gt;
        /// Methuselah Pattern - can evolve for a long time before stabilizing.
        /// &lt;/summary&gt;
        public static readonly int[] RPentomino = new[] {
                                                            // Dimensions                                
                                                            4, 4,
                                                            // Pattern
                                                            0, 1, 1, 0,
                                                            1, 0, 0, 1,
                                                            0, 1, 0, 1,
                                                            0, 0, 1, 0,
                                                        };

        /// &lt;summary&gt;
        /// Methuselah Pattern - can evolve for a long time before stabilizing.
        /// This one disappears after 130 generations
        /// &lt;/summary&gt;
        public static readonly int[] Diehard = new[] {
                                                         // Dimensions                                
                                                         8, 3,
                                                         // Pattern
                                                         0, 0, 0, 0, 0, 0, 1, 0,
                                                         1, 1, 0, 0, 0, 0, 0, 0,
                                                         0, 1, 0, 0, 0, 1, 1, 1,
                                                     };

        /// &lt;summary&gt;
        /// Methuselah Pattern - can evolve for a long time before stabilizing.
        /// This one disappears after 130 generations
        /// &lt;/summary&gt;
        public static readonly int[] Acorn = new[] {
                                                       // Dimensions                                
                                                       7, 3,
                                                       // Pattern
                                                       0, 1, 0, 0, 0, 0, 1,
                                                       0, 0, 0, 1, 0, 0, 0,
                                                       1, 1, 0, 0, 1, 1, 1
                                                   };

// Infinite Growth Patterns:
        /// &lt;summary&gt;
        /// Infinite Growth Pattern - with only 10 live cell (which proven to be mnimal)
        /// &lt;/summary&gt;
        public static readonly int[] InfiniteGrowth1 = new[] {
                                                                 // Dimensions                                
                                                                 8, 6,
                                                                 // Pattern
                                                                 0, 0, 0, 0, 0, 0, 1, 0,
                                                                 0, 0, 0, 0, 1, 0, 1, 1,
                                                                 0, 0, 0, 0, 1, 0, 1, 0,
                                                                 0, 0, 0, 0, 1, 0, 0, 0,
                                                                 0, 0, 1, 0, 0, 0, 0, 0,
                                                                 1, 0, 1, 0, 0, 0, 0, 0
                                                             };

        /// &lt;summary&gt;
        /// Infinite Growth Pattern - from a mere 5x5 pattern
        /// &lt;/summary&gt;
        public static readonly int[] InfiniteGrowth2 = new[] {
                                                                 // Dimensions                                
                                                                 5, 4,
                                                                 // Pattern
                                                                 1, 1, 1, 0, 1,
                                                                 1, 0, 0, 0, 0,
                                                                 0, 0, 0, 1, 1,
                                                                 0, 1, 1, 0, 1,
                                                                 1, 0, 1, 0, 1
                                                             };

        /// &lt;summary&gt;
        /// Infinite Growth Pattern - only one cell high
        /// &lt;/summary&gt;
        public static readonly int[] InfiniteGrowth3 =
            new[] {
                      // Dimensions                                
                      39, 1,
                      // Pattern
                      1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1
                      , 1, 0, 1, 1, 1, 1, 1
                  };

        /// &lt;summary&gt;
        /// The World's first Infinite Growth Pattern - Gosper Glider Gun.
        /// Developed at MIT in 1970 by a team lead by Bill Gosper.
        /// Proved for the first time that infinite growth is possbile in Game of Life.
        /// ...They won a $50 prize from John Conway (the inventor of Game of Life (and apparently a cheapskate?).
        /// &lt;/summary&gt;
        public static readonly int[] GosperGliderGun =
            new[] {
                      // Dimensions                                
                      36, 9,
                      // Pattern
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0
                      , 0, 0, 0, 0,
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0
                      , 0, 0, 0, 0,
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
                      , 0, 0, 1, 1,
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
                      , 0, 0, 1, 1,
                      1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
                      , 0, 0, 0, 0,
                      1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0
                      , 0, 0, 0, 0,
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0
                      , 0, 0, 0, 0,
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
                      , 0, 0, 0, 0,
                      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
                      , 0, 0, 0, 0,
                  };

        private static readonly int[][] Patterns = new[] {
                                                             Blinker,
                                                             Toad,
                                                             Beacon,
                                                             Pulsar,
                                                             Block,
                                                             Beehive,
                                                             Loaf,
                                                             Boat,
                                                             Glider,
                                                             LightweightSpaceship,
                                                             RPentomino,
                                                             Diehard,
                                                             Acorn,
                                                             InfiniteGrowth1,
                                                             InfiniteGrowth2,
                                                             InfiniteGrowth3,
                                                             GosperGliderGun
                                                         };
    }
}</pre></div></div><hr /><table width="100%"><tr><td valign="top"><span class="copyright">Copyright (c) Microsoft Corporation. All rights reserved.</span><br /><span class="button" onclick="copySourceToClipboard()">Copy full source to clipboard</span></td></tr></table><div id="debugdiv"> </div></body></html>